package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-02-23 21:48
 */
class ResultType2 {
    boolean pExist;
    boolean qExist;
    TreeNode node;

    public ResultType2(boolean pExist, boolean qExist, TreeNode node) {
        this.pExist = pExist;
        this.qExist = qExist;
        this.node = node;
    }
}

public class QLint578 {
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
        ResultType2 helper = helper(root, p, q);
        if (helper.pExist && helper.qExist) {
            return helper.node;
        } else {
            return null;
        }
    }

    private ResultType2 helper(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return new ResultType2(false, false, null);
        }

        ResultType2 left = helper(root.left, p, q);
        ResultType2 right = helper(root.right, p, q);

        boolean pExist = left.pExist || right.pExist || root == p;
        boolean qExist = left.qExist || right.qExist || root == q;

        if (root == p || root == q) {
            return new ResultType2(pExist, qExist, root);
        }

        if (left.node != null && right.node != null) {
            return new ResultType2(pExist, qExist, root);
        }
        if (left.node != null) {
            return new ResultType2(pExist, qExist, left.node);
        }
        if (right.node != null) {
            return new ResultType2(pExist, qExist, right.node);
        }
        return new ResultType2(pExist, qExist, null);
    }
}
